计算机与数学——三角形内生成均匀的随机点

这篇博客介绍了数学上如何在三角形内生成均匀随机点的方法。

在进行HairStrandPlugin的迭代过程中，有涉及到发丝间插值的需求。因此研究了一下在三角形内部进行均匀随机点的生成方法。

需求

现在有三个点 a,b,c 构成一个三角形。现在需要在这个三角形内部进行随机点的生成，当足够多的点被生成时，这些点在三角形内的分布需要为均匀分布。

思考

barycentric coordinates

在三角形内的任意一点 P ，都存在着 0≤u,v≤1 使得

因此最初的思考是直接对 u,v 在 0≤u,v≤1 与 0≤u+v≤1 取任意值。

可是这样一来无法达到均匀分布的需求，例如三角形最长的那条边上的点会分布的较为稀疏。

能够生成均匀随机点的方法

我在Graphic Gem Ⅰ中找到了两种可以生成均匀随机点的方法。

Method 1

令 s,t 在区间 [0,1] 之间取值，随机点 Q 的值依靠以下算法获得：

a←1−t√ ;
b←(1−s)t√ ;
c←st√ ;
Q←aA+bB+cC ;

在以上的算法中，我们使用变量 t 来获得一条平行于 BC 并且与 AB 和 AC 相交的直线，并且在这条线段上根据 s 来获得这个点。

需要注意的是这里使用到了 t√ 而不是简单的 t 来进行操作。这是因为均匀分布是根据面积来判定的，因此上层三角形的面积是与高度的平方成正比，因此此处需要使用 t√ 来进行操作。

Method 2

令 s,t 在区间 [0,1] 之间取值，随机点 Q 的值依靠以下算法获得：

if s+t>1 then
        begin
        s←1−s
        t←1−t
        end
a←1−s−t ;
b←s ;
c←t ;
Q←aA+bB+cC ;

如果我们把if语句去掉，实际上上面的算法是求出了一个在平行四边形 (A,B,C,B+C−A) 内的随机点。

如果这个随机点位于三角形 (B,C,B+C−A) 中，则通过 BC 边反射到三角形 (A,B,C) 内即可。

推演到高维

Method 1可以很方便得扩展到高维，例如，如果我们需要在四面体内生成均匀的随机点，则只需要三个随机数。第一个数获得与底面平行的面，而后两个数则在这个面上进行随机点选取。

Method 2想要扩展到高维就麻烦不少了。给出 r,s,t 三个点，我们可以使用这三个点来获得一个平行六面体中的随机点。但是平行六面体想要切割成两个全等的四面体是挺麻烦的，因此直接取点然后进行反射的方法不太实际。

但是实际上我们可以进行 r+s+t>1 的条件判断来筛选出那些在六面体中而不在原四面体中的点，直接忽视之即可。

—全文完—